package com.ntd.study.base.type.tree;

/**
 * 二叉树工具
 *
 * @author liuwenju
 * @date 2021/5/6 11:17
 */
public class BinaryTree<T> {

    private BinaryTreeNode<T> rootNode;
    private int length = 0;

    /**
     * 查找节点
     * @param key
     * @return
     */
    public BinaryTreeNode<T> get(int key) {
        if (rootNode == null) {
            return null;
        }
        return find(rootNode, key);
    }
    private BinaryTreeNode<T> find(BinaryTreeNode<T> currentNode, int key) {
        if (currentNode == null) {
            return null;
        }
        if (currentNode.getKey() == key) {
            return currentNode;
        }
        if (currentNode.getKey() > key) {
            return find(currentNode.getLeftNode(), key);
        } else {
            return find(currentNode.getRightNode(), key);
        }
    }

    public void add(int key, T data) {
        BinaryTreeNode<T> newNode = new BinaryTreeNode<T>(key, data);
        //如果第一个节点为空 设置第一个节点
        if (rootNode == null) {
            rootNode = newNode;
        } else {
            insert(rootNode, newNode);
        }
        length++;
    }

    /**
     * 添加节点
     * @param currentNode
     * @param insertNode
     * @return
     */
    private void insert(BinaryTreeNode<T> currentNode, BinaryTreeNode<T> insertNode) {
        if (currentNode.getKey() > insertNode.getKey()) {
            if (currentNode.getLeftNode() != null) {
                insert(currentNode.getLeftNode(), insertNode);
            }
            currentNode.setLeftNode(insertNode);
        } else {
            if (currentNode.getRightNode() != null) {
                insert(currentNode.getRightNode(), insertNode);
            }
            currentNode.setRightNode(insertNode);
        }
    }


    /**
     * 查看长度
     * @return
     */
    public int length() {
        return length;
    }
}
